package com.example.algorithm.service.impl;

import com.example.algorithm.service.StackService;
import org.springframework.stereotype.Service;

import java.time.temporal.TemporalAccessor;
import java.util.*;

/** 栈
 * @auth Administrator
 * @create @2024/8/5@21:50
 * @decription
 **/
@Service
public class StackServiceImpl implements StackService {
    /**
     *NO.68 有效的括号
     *
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     *
     * 有效字符串需满足：
     *
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 每个右括号都有一个对应的相同类型的左括号。
     * @param s
     * @return
     * 解法一：栈
     *
     *
     *
     */
    @Override
    public boolean isValid(String s) {
        char [] str = s.toCharArray();
        Map<Character ,Character > para = new HashMap<>();
        para.put('(',')');
        para.put('{','}');
        para.put('[',']');
        if(s.length() > 0 && !para.containsKey(s.charAt(0))) {
            return false;
        }
        Stack stack = new Stack<Character>();
        for(char c:str){
            if(para.containsKey(c)){
                stack.push(c);
            }else{
                if(stack.isEmpty()){
                    return false;
                }

                if(para.get(stack.pop())!=c){
                    return false;
                }
            }


        }

        return stack.size()==0;
    }

    /**NO.69 字符串解码
     * 给定一个经过编码的字符串，返回它解码后的字符串。
     *
     * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
     *
     * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
     *
     * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
     *
     *
     * @param s
     * @return
     * 解法一：栈
     * 解法二：递归
     * 解法三：辅助stringbuffer
     *
     *
     */
    @Override
    public String decodeString(String s) {
        if(s.indexOf('[')==-1||s.indexOf(']')==-1){
            return s;
        }
        Stack stack = new Stack<>();
        int num=0;
        StringBuffer sb = new StringBuffer();
        for(char c :s.toCharArray()){
            if(Character.isDigit(c)){
                num = num*10+c-'0';
            }else if(c=='['){
                stack.push(num);
                num=0;
                stack.push(sb);
                sb =new StringBuffer();
            }else if(Character.isLetter(c)){
                sb.append(c);
            }else{
                StringBuffer  temp = (StringBuffer)stack.pop();
                int count = (Integer)stack.pop();
                for(int j=0;j<count;j++){
                    temp.append(sb);
                }
                sb = temp;
            }
        }
        return sb.toString();
    }

    /**NO.70 每日温度
     * 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
     * @param temperatures
     * @return
     * 解法一：暴力
     *
     */
    @Override
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack();
        int[] res = new int[temperatures.length];
        stack.push(0);
        for(int i=1;i<temperatures.length;i++ ){
          while (!stack.isEmpty()&&temperatures[stack.peek()]<temperatures[i]){
              int tmp = stack.pop();
              res[tmp]=i-tmp;
          }
            stack.push(i);
        }
        return res;
    }

    /**NO.71 柱状图最大的矩形
     * 难度：困难
     * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
     *
     * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
     * @param heights
     * @return
     * 解法一：暴力查询
     * 方法二：单调栈
     * 解法三：单调栈 + 常数优化
     * 解法四：辅助数组
     *
     */
    @Override
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack();
        int[] tmp = new int[heights.length + 2];
        System.arraycopy(heights, 0, tmp, 1, heights.length);
        int maxArea = 0;
        for(int i=0;i<tmp.length;i++ ){
            while (!stack.isEmpty()&&tmp[stack.peek()]>tmp[i]){
                int height = tmp[stack.pop()];
                maxArea =Math.max(maxArea,height*(i-stack.peek()-1));
            }
            stack.push(i);
        }
        return maxArea;
    }


    /**
     * No.921 使括号有效的最少添加（难度：中等）
     *只有满足下面几点之一，括号字符串才是有效的：
     * 1)它是一个空字符串，或者
     * 2)它可以被写成 AB(A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
     * 3)它可以被写作 (A)，其中 A 是有效字符串。
     * 给定一个括号字符串 s ，移动N次，你就可以在字符串的任何位置插入一个括号。
     * 例如，如果 s = "()))" ，你可以插入一个开始括号为 "(()))" 或结束括号为 "())))"。
     * 返回 为使结果字符串 s 有效而必须添加的最少括号数
     * 思路1：利用栈特性去计算
     * 思路2：找规律去匹配
     *
     * @param s
     * @return
     */
    @Override
    public int minAddToMakeValid(String s) {
        Deque<Character> deque = new ArrayDeque<>();
        for(char c : s.toCharArray()){
            if(deque.size()!=0&&deque.peekLast().equals('(')&& c==')'){
                deque.removeLast();
            }else{
                deque.addLast(c);
            }
        }
        return deque.size();
    }

    public int minAddToMakeValid1(String s) {
      int leftCount=0,rightCount=0;
      for(char c :s.toCharArray()){
          if(c=='('){
              leftCount++;
          }else {
              if(leftCount==0){
                  rightCount++;
              }else{
                  leftCount--;
              }
          }


      }

      return  rightCount+leftCount;
    }
}
